In material set theory, especially versions of set theory that accept the axiom of foundation that the membership relation is an extensional (but not necessarily transitive) well-founded relation, there is a picture of sets as forming a cumulative hierarchy, hierarchically ordered by a rank function valued in the ordinals. The idea is that on Day 0 the empty set is born; on Day is born the power set of Day . On limit Days all the sets born earlier are collected together into a single set which is their union. The cumulative hierarchy picture amounts to the assertion that every set belongs to some set produced by this iterative procedure.
Suppose is a model of ZFC. Recall that in the theory ZFC, a set is defined to be transitive if implies ; this is the same as saying that if then . Note this doesn’t mean that the relation on the set consisting of and the elements of its transitive closure is itself transitive: the condition concerns only chains where . However, if that relation is transitive, then it is transitive, and extensional (by the extensionality axiom), and well-founded (by the axiom of foundation), and hence a well-order according to the argument here. In this case, is by definition an ordinal number (in the sense of von Neumann).
Letting be the class of ordinals (= ordinal numbers), one may define with the help of the replacement axiom a function
by transfinite induction as follows: , while
(where denotes power set),
when is a limit ordinal.
Each of the is transitive, and implies .
First, if is a transitive set, then so is . For suppose . Then , and so if , we have and thus since is transitive, so that . We have thus shown .
That each is transitive now follows by an easy induction.
And so since , and now follows by an easy induction.
If , then there is a least such that , and this must be a successor ordinal, . We define the rank of to be that . Thus
has rank ,
has rank ,
and have rank ,
and so on. Each ordinal has rank .
For every element of , there is some such that . Thus every set appears as an element somewhere within the cumulative hierarchy
The proof is essentially that is an -inductive set of , and so must be all of since is well-founded (by the axiom of foundation). Details may be found in any reasonable text on ZFC set theory, for example Kunen.
The notation so widely seen in set theory texts and articles is a kind of visual pun that refers to the cumulative hierarchy: one imagines the V as outlining an angle, with a horizontal cross-section of the space inside the angle at height suggesting a set , which expands as increases; the ordinals themselves may be pictured as vertebrae of a spine or line therein. All sets in the cumulative hierarchy lie somewhere within the V.
The idea of the cumulative hierarchy is realized in algebraic set theory via the construction of an initial “ZF-algebra”. In broad-brush terms, there is a general connection between well-foundedness and initial algebras, as in Paul Taylor’s theory of recursion where an initial -algebra (for a taut functor ) is seen as a well-founded coalgebra for which is an isomorphism (i.e., a maximal well-founded coalgebra). Algebraic set theory can be seen as exploiting this connection and working out the details in cases specific to operations on “small sets”, eventually enabling one to get at the cumulative hierarchy per se, i.e., the universe of well-founded sets (as well as the universe of ordinals, etc.).
This deserves to be discussed at length, but let us try to give a few hints for now. One starts with a pretopos (whose objects are regarded as “classes”) equipped with a suitable notion of “smallness”: to say a map in the pretopos is “small” means intuitively that all its fibers are “small” (i.e., sets). Thus one assumes some reasonable axioms on the class of small maps in , including the existence of a universal small map “”: , with the elements of naming small sets and the fiber over the actual (small) set of its elements. The smallness axioms allow one to construct a small-power set functor ; intuitively this sends a class to the class of small subsets of . This carries a monad structure whose algebras are “small-complete” posets in .
To get at the actual cumulative hierarchy (with attendant global membership relation ), one defines a ZF-algebra to be a small-complete poset in , equipped with a function satisfying suitable conditions; here one is to think of as “inclusion” and as a singleton . The relation can then be interpreted as . The initial object in the category of ZF-algebras then captures the desired universe of well-founded sets.
The details of the construction of the initial ZF-algebra should be examined with attention to connections with Taylor’s theory of well-founded coalgebras; for example, systematic use is made of bisimulations which has a general meaning in coalgebra theory.
This program, initiated by André Joyal and Ieke Moerdijk, permits a fine-grained analysis of intuitionistic ZF-set theory and intuitionistic ordinals. The reader is referred to their monograph for details, and to the Algebraic Set Theory page for further pointers to the literature.
The cumulative hierarchy made its first appearance in
Another historically important contribution is
A modern textbook account can be found e.g. in
For algebraic set theory consult the following monograph
Last revised on April 10, 2019 at 16:00:21. See the history of this page for a list of all contributions to it.